/*-
 * Copyright (c) 2012 CTPP Team
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 4. Neither the name of the CTPP Team nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *      BPlusTree.hpp
 *
 * $CTPP$
 */

/**
  @file BPlusTree.hpp
  This file contains realization of generic B+Tree.
*/

#ifndef _BPLUS_TREE_HPP__
#define _BPLUS_TREE_HPP__ 1

#include "Types.h"
#include <stdio.h>
#include <fcntl.h>
#include <STLVector.hpp>
#include <iostream>
#include <sys/types.h>
#include <Pair.hpp>
#include <BPlusNodeLeaf.hpp>
#include <BPlusCache.hpp>
namespace MAIL
{


/**
  @class BPlusTree BPlusTree.hpp <BPlusTree.hpp>
  @brief Generic B+Tree.

  B+ trees are balanced trees which provide an ordered map from keys to values.
<pre>
                        |350|                |779|                    |1159|        | Root node
                        /   \                /   \                    /   \
                    ---      ---          ---    ---               ---     |
                   /            \        /          \             /        |
|89 |155|196|276|350*| |446|540|655|724|779*| |808|917|1030|1101|1159*|    |        | Leafs
|100|101|102|103|104*| |105|106|107|108|109*| |110|111|112 |113 |114 *|    |        |
                                                                          /         |
                            |1192|1222|1232|1329|1425|1474|1587|1608|1679|1692|     |
                            |115 |116 |117 |118 |119 |120 |121 |122 |123 |124 |     |

</pre>
*/

template <typename T, typename V, INT_64 TreeWidth>class BPlusTree
{
private:
	// tree meta information
	INT_64 max_entries;
	INT_64 min_entries;
	INT_64 tree_size;
	// storage HDD with cache
	FTSS::BPlusCache<T, V, TreeWidth> *cacheHDDStorage;
public:
	// id root node (or leaf)
	INT_64 root;

	/**
	* @brief Constructor
	* @param pNodeStorageName - name for storage nodes of HDD
	* @param pNodeStorageWhiteSpaceName - name for vector of white space in node storage
	* @param pLeafStorageName - name for storage leafs of HDD
	* @param pLeafStorageWhiteSpaceName - name for vector of white space in leaf storage
	*/
	BPlusTree( CCHAR_P pNodeStorageName,
                   CCHAR_P pNodeStorageWhiteSpaceName,
                   CCHAR_P pLeafStorageName,
                   CCHAR_P pLeafStorageWhiteSpaceName);

	/**
	  @return the size of the tree
	*/
	inline INT_64 size() { return tree_size; }

	/**
	* @brief check tree 
	* @return true if tree is empty, false if not
	*/
	inline bool isEmpty() { return (tree_size == 0); }


	/**
	* @brief search values between min_entry and max_entry keys
	* @param min_entry - minimal key for search
	* @param max_entry - maxinmal key for search
	* @return vector of values for all keys between min and max entries
	*/
	STLW::vector<V*> *search(T min_entry, T max_entry);

	/**
	* @brief return raw data of values
	* @return pointer to data raw
	*/	
	CHAR_P search_array(T min_entry, T max_entry, INT_32 number_ans, INT_32 &docEntrySize);
	
	/**
	* @brief search key in tree and increment size field (entry.size)
	*/
	void search_and_increment_and_add_DF(const T &entry);
	/**
	* @brief check contains tree key or not
	* @return -1 if not contatins, entry.size if contains
	*/
	INT_64 contains(const T & entry);

	/**
	* @biref get DF field for key
	*/
	INT_64 getIDF(T entry);

	/**
	  @brief Insert element in a tree
	  @param oPair - data to insert
	  @return false if duplicate element found
	 */
	bool Insert(const Pair<T, V> & oPair);

	/**
	* @brief Insert key and value in tree
	* @param 
	*/
	inline bool Insert(const T &oNode, const V &oLeaf){
//		Pair <T, V> *oInsertPair = new Pair<T, V> (oNode, oLeaf);
		return this->Insert(Pair<T, V> (oNode, oLeaf));

	}
	/**
	* @brief remove key and value from tree
	* @return true if success, false if fail
	*/
	bool Remove(const T & tKey);

	/**
	* @brief print to stderr tree using depth first search algorytm
	*/
	void DFSPrintTree();

	class iterator{
	};

	/**
	* @Destructor
	*/
	~BPlusTree();
private:
	/**
	* @brief recursive deepth first search printing
	* @oaram current_node - current id of node or leaf
	*/
	void DFSPrintTreeRec(INT_64 current_node, bool first);
	/**
	  @brief Recursive insertion in tree
	  @param pType - current leaf/node
	  @param oPair - data to insert
	  @param pNewType - newly created leaf/node
	  @param tValue - insertted/moved key
	  @return false if duplicate element found
	*/
	bool InsertRec(INT_64            pType,
	               const Pair<T, V>  & oPair,
	               INT_64            & pNewType,
	               T                 & tValue,
		       bool                first);

	INT_64 SearchLeaf(INT_64 pLeaf, const T & tKey);

	INT_64 SearchNode(INT_64 pNode, const T & tKey);

	INT_64 BisectLeftLeaf(INT_64         pLeaf,
	                      const T      & tKey,
	                      INT_64         iStartPos,
	                      const INT_64   iEndPos);

	INT_64 BisectLeftNode(INT_64         pNode,
	                      const T      & tKey,
	                      INT_64         iStartPos,
	                      const INT_64   iEndPos);


	bool RemoveRec(INT_64    pThisType,
	               INT_64    pLeftType,
	               INT_64    pRightType,
	               INT_64    left_anchor,
	               INT_64    right_anchor,
	               const T & entry,
		       bool      first);
	/**
	  @brief Merge two leafs
	  @param pLeftNode - left leaf
	  @param pRightNode - right leaf
	  @param pParentNode - parent node
	*/
	void ShiftLeafs(INT_64  this_node,
	                INT_64  neighbor_node,
	                INT_64  anchor_node,
	                bool    copy_from_right);

	/**
	  @brief Merge two leafs
	  @param pLeftNode - left leaf
	  @param pRightNode - right leaf
	  @param pParentNode - parent node
	*/
	void ShiftNodes(INT_64  pThisNode,
	                INT_64  pSibling,
	                INT_64  pParentNode,
	                bool    copy_from_right);

	/**
	  @brief Merge two leafs
	  @param pLeftNode - left leaf
	  @param pRightNode - right leaf
	  @param pParentNode - parent node
	*/
	void MergeLeafs(INT_64   pLeftNode,
	                INT_64   pRightNode,
	                INT_64   pParentNode);
	/**
	  @brief Merge two nodes
	  @param pLeftNode - left node
	  @param pRightNode - right node
	  @param pParentNode - parent node
	*/
	void MergeNodes(INT_64   pLeftNode,
	                INT_64   pRightNode,
	                INT_64   pParentNode);
	/**
	  @brief Get node or leaf from right storage and return pointer
	*/
	BPlusNodeType* getById(INT_64 id, bool clearMemory);

	/**
	* @brief get leaf for entry 
	* @param node current node id
	* @param entry - key
	*/
	BPlusNodeType* getLeaf(INT_64 node, T entry);

	/**
	  @brief Dump node or leaf to right storage
	  @param node_type - current pointer to node type in tree
	*/
	INT_64 dumpNodeType(BPlusNodeType *node_type);
	/**
	* @brief delete node of leaf from HDD
	* @param node_type - node_type to delete
	*/
	void deleteNodeType(BPlusNodeType *node_type);
};

} // namespace MAIL

#include "BPlusTree.tcc"

#endif // _BPLUS_TREE_HPP__
// End.
